SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Functional completeness</title>

</head>

Functional completeness

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1246091330">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><table class="sidebar nomobile nowraplinks"><tbody><tr><th class="sidebar-title" style="font-size: 130%; margin: 6px 0px 6px 0px; background: #ddf;"><a href="Logical_connective" title="Logical connective">Logical connectives</a></th></tr><tr><td class="sidebar-content">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \neg A,-A,{\overline {A}},\sim A}</annotation>

</semantics>

</math><img src="./8eab858e54d8de87e36fc80a991b32e74201a600.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.001ex; height:3.343ex;" alt="{\displaystyle \neg A,-A,{\overline {A}},\sim A}" loading="lazy"></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Logical_conjunction" title="Logical conjunction">AND</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\land B,A\cdot B,AB,A\ \&\ B,A\ \&\&\ B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\land B,A\cdot B,AB,A\ \&\ B,A\ \&\&\ B}</annotation>

</semantics>

</math><img src="./c041e99940ccd418648ea18d200af37e2b3548d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:33.68ex; height:2.509ex;" alt="{\displaystyle A\land B,A\cdot B,AB,A\ \&\ B,A\ \&\&\ B}" loading="lazy"></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Sheffer_stroke" title="Sheffer stroke">NAND</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A{\overline {\land }}B,A\uparrow B,A\mid B,{\overline {A\cdot B}}}">

<mover>

</mover>

</mrow>

<mover>

<mrow>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A{\overline {\land }}B,A\uparrow B,A\mid B,{\overline {A\cdot B}}}</annotation>

</semantics>

</math><img src="./b05374b45c2316947f052c6a46ca0f1d9381ed0e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.98ex; height:3.509ex;" alt="{\displaystyle A{\overline {\land }}B,A\uparrow B,A\mid B,{\overline {A\cdot B}}}" loading="lazy"></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Logical_disjunction" title="Logical disjunction">OR</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\lor B,A+B,A\mid B,A\parallel B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\lor B,A+B,A\mid B,A\parallel B}</annotation>

</semantics>

</math><img src="./a262d8ab1dd1738c2b888661fe847101b624992d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.943ex; height:2.843ex;" alt="{\displaystyle A\lor B,A+B,A\mid B,A\parallel B}" loading="lazy"></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Logical_NOR" title="Logical NOR">NOR</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A{\overline {\lor }}B,A\downarrow B,{\overline {A+B}}}">

<mover>

</mover>

</mrow>

<mover>

<mrow>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A{\overline {\lor }}B,A\downarrow B,{\overline {A+B}}}</annotation>

</semantics>

</math><img src="./331ccd940d0039678505e971d3e13a63fca14354.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.663ex; height:3.343ex;" alt="{\displaystyle A{\overline {\lor }}B,A\downarrow B,{\overline {A+B}}}" loading="lazy"></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="XNOR_gate" title="XNOR gate">XNOR</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\odot B,{\overline {A{\overline {\lor }}B}}}">

<mover>

<mrow>

<mover>

</mover>

</mrow>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\odot B,{\overline {A{\overline {\lor }}B}}}</annotation>

</semantics>

</math><img src="./7e5a7f5c2cebe8c2903dea347e6ce9223cc47e13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.669ex; height:3.843ex;" alt="{\displaystyle A\odot B,{\overline {A{\overline {\lor }}B}}}" loading="lazy"></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> └ <a href="Logical_biconditional" title="Logical biconditional">equivalent</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B}</annotation>

</semantics>

</math><img src="./73fd8a2bddea3e7553e1905a4b2b8944269d5430.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:22.916ex; height:2.509ex;" alt="{\displaystyle A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B}" loading="lazy"></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Exclusive_or" title="Exclusive or">XOR</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A{\underline {\lor }}B,A\oplus B}">

</munder>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A{\underline {\lor }}B,A\oplus B}</annotation>

</semantics>

</math><img src="./d48ea5022d9d865ea81c6f954cf73429be684009.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.562ex; margin-bottom: -0.776ex; width:12.441ex; height:3.176ex;" alt="{\displaystyle A{\underline {\lor }}B,A\oplus B}" loading="lazy"></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> └ nonequivalent</td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B}</annotation>

</semantics>

</math><img src="./e31480781c46a0001e81f596615bc56e20d8aaa6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.917ex; height:2.676ex;" alt="{\displaystyle A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B}" loading="lazy"></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Material_conditional" title="Material conditional">implies</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\Rightarrow B,A\supset B,A\rightarrow B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\Rightarrow B,A\supset B,A\rightarrow B}</annotation>

</semantics>

</math><img src="./da2d4ee4d40286755cb17f11743dcece3224fa90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:22.916ex; height:2.509ex;" alt="{\displaystyle A\Rightarrow B,A\supset B,A\rightarrow B}" loading="lazy"></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Material_nonimplication" title="Material nonimplication">nonimplication</a> (<a href="NIMPLY_gate" title="NIMPLY gate">NIMPLY</a>)</td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\not \Rightarrow B,A\not \supset B,A\nrightarrow B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\not \Rightarrow B,A\not \supset B,A\nrightarrow B}</annotation>

</semantics>

</math><img src="./4d66f3ed3dc468f35292dfe91a75d59b3b5d4915.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.917ex; height:2.676ex;" alt="{\displaystyle A\not \Rightarrow B,A\not \supset B,A\nrightarrow B}" loading="lazy"></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Converse_(logic)" title="Converse (logic)">converse</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\Leftarrow B,A\subset B,A\leftarrow B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\Leftarrow B,A\subset B,A\leftarrow B}</annotation>

</semantics>

</math><img src="./128eb93aed65dd2e3aa1a4aaef4171a44f9a6718.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:22.916ex; height:2.509ex;" alt="{\displaystyle A\Leftarrow B,A\subset B,A\leftarrow B}" loading="lazy"></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Converse_nonimplication" title="Converse nonimplication">converse nonimplication</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\not \Leftarrow B,A\not \subset B,A\nleftarrow B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\not \Leftarrow B,A\not \subset B,A\nleftarrow B}</annotation>

</semantics>

</math><img src="./651dce7a12fa2331a8c610ee47b32982552a01f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.917ex; height:2.676ex;" alt="{\displaystyle A\not \Leftarrow B,A\not \subset B,A\nleftarrow B}" loading="lazy"></td></tr></tbody></table></td>

</tr><tr><th class="sidebar-heading" style="background: #eef; text-align: center;">

Related concepts</th></tr><tr><td class="sidebar-content">

<div class="hlist" style="line-height:1.3em;"><ul><li><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional calculus</a></li><li><a href="First-order_logic" title="First-order logic">Predicate logic</a></li><li><a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a></li><li><a href="Truth_table" title="Truth table">Truth table</a></li><li><a href="Truth_function" title="Truth function">Truth function</a></li><li><a href="Boolean_function" title="Boolean function">Boolean function</a></li><li><a href="Scope_(logic)" title="Scope (logic)">Scope (logic)</a></li></ul></div></td>

</tr><tr><th class="sidebar-heading" style="background: #eef; text-align: center;">

Applications</th></tr><tr><td class="sidebar-content">

<div class="hlist"><ul><li><a href="Logic_gate" title="Logic gate">Digital logic</a></li><li><a href="Programming_language" title="Programming language">Programming languages</a></li><li><a href="Mathematical_logic" title="Mathematical logic">Mathematical logic</a></li><li><a href="Philosophy_of_logic" title="Philosophy of logic">Philosophy of logic</a></li></ul></div></td>

</tr><tr><td class="sidebar-below hlist" style="background: #eef; text-align: center;">

Category</td></tr><tr><td class="sidebar-navbar"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

In <a href="Mathematical_logic" title="Mathematical logic">logic</a>, a functionally complete set of <a href="Logical_connective" title="Logical connective">logical connectives</a> or <a href="Boolean_function" title="Boolean function">Boolean operators</a> is one that can be used to express all possible <a href="Truth_table" title="Truth table">truth tables</a> by combining members of the <a href="Set_(mathematics)" title="Set (mathematics)">set</a> into a <a href="Boolean_expression" title="Boolean expression">Boolean expression</a>.<a href="#cite_note-Enderton2001-1">[1]</a><a href="#cite_note-Nolt1998-2">[2]</a> A well-known complete set of connectives is { <a href="Logical_conjunction" title="Logical conjunction">AND</a>, <a href="Negation" title="Negation">NOT</a> }. Each of the <a href="Singleton_(mathematics)" title="Singleton (mathematics)">singleton</a> sets { <a href="Sheffer_stroke" title="Sheffer stroke">NAND</a> } and { <a href="Logical_NOR" title="Logical NOR">NOR</a> } is functionally complete. However, the set { AND, <a href="Logical_disjunction" title="Logical disjunction">OR</a> } is incomplete, due to its inability to express NOT.

A gate (or set of gates) that is functionally complete can also be called a universal gate (or a universal set of gates).

In a context of <a href="Propositional_logic" title="Propositional logic">propositional logic</a>, functionally complete sets of connectives are also called (expressively) adequate.<a href="#cite_note-Smith2003-3">[3]</a>

From the point of view of <a href="Digital_electronics" title="Digital electronics">digital electronics</a>, functional completeness means that every possible <a href="Logic_gate" title="Logic gate">logic gate</a> can be realized as a network of gates of the types prescribed by the set. In particular, all logic gates can be assembled from either only binary <a href="NAND_gate" title="NAND gate">NAND gates</a>, or only binary <a href="NOR_gate" title="NOR gate">NOR gates</a>.

<div class="mw-heading mw-heading2"><h2 id="Introduction">Introduction</h2></div>

Modern texts on logic typically take as primitive some subset of the connectives: <a href="Logical_conjunction" title="Logical conjunction">conjunction</a> (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \land }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \land }</annotation>

</semantics>

</math><img src="./d6823e5a222eb3ca49672818ac3d13ec607052c4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.009ex;" alt="{\displaystyle \land }" loading="lazy">); <a href="Logical_disjunction" title="Logical disjunction">disjunction</a> (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lor }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lor }</annotation>

</semantics>

</math><img src="./ab47f6b1f589aedcf14638df1d63049d233d851a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.009ex;" alt="{\displaystyle \lor }" loading="lazy">); <a href="Negation" title="Negation">negation</a> (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \neg }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \neg }</annotation>

</semantics>

</math><img src="./fa78fd02085d39aa58c9e47a6d4033ce41e02fad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.204ex; margin-bottom: -0.376ex; width:1.55ex; height:1.176ex;" alt="{\displaystyle \neg }" loading="lazy">); <a href="Material_conditional" title="Material conditional">material conditional</a> (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \to }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \to }</annotation>

</semantics>

</math><img src="./1daab843254cfcb23a643070cf93f3badc4fbbbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \to }" loading="lazy">); and possibly the <a href="Logical_biconditional" title="Logical biconditional">biconditional</a> (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \leftrightarrow }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \leftrightarrow }</annotation>

</semantics>

</math><img src="./046b918c43e05caf6624fe9b676c69ec9cd6b892.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \leftrightarrow }" loading="lazy">). Further connectives can be defined, if so desired, by defining them in terms of these primitives. For example, NOR (the negation of the disjunction, sometimes denoted <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \downarrow }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \downarrow }</annotation>

</semantics>

</math><img src="./4618f22b0f780805eb94bb407578d9bc9487947a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.162ex; height:2.509ex;" alt="{\displaystyle \downarrow }" loading="lazy">) can be expressed as conjunction of two negations:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\downarrow B:=\neg A\land \neg B}</annotation>

</semantics>

</math><img src="./0abb0639bb9abb6e770f0176959cf6aecec81a7e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.896ex; height:2.509ex;" alt="{\displaystyle A\downarrow B:=\neg A\land \neg B}" loading="lazy"></dd></dl>

Similarly, the negation of the conjunction, NAND (sometimes denoted as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \uparrow }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \uparrow }</annotation>

</semantics>

</math><img src="./ddb20b28c74cdaa09e1f101d426441da1996072f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.162ex; height:2.509ex;" alt="{\displaystyle \uparrow }" loading="lazy">), can be defined in terms of disjunction and negation. Every binary connective can be defined in terms of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}</annotation>

</semantics>

</math><img src="./54b4874f437697d5ff55f5d020caf59e8ca11395.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.759ex; height:2.843ex;" alt="{\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}" loading="lazy">, which means that set is functionally complete. However, it contains redundancy: this set is not a minimal functionally complete set, because the conditional and biconditional can be defined in terms of the other connectives as

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}A\to B&:=\neg A\lor B\\A\leftrightarrow B&:=(A\to B)\land (B\to A).\end{aligned}}}</annotation>

</semantics>

</math><img src="./2d673bf84fe5b3cf8aa3a7f15df80d99388b2776.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:32.708ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}A\to B&:=\neg A\lor B\\A\leftrightarrow B&:=(A\to B)\land (B\to A).\end{aligned}}}" loading="lazy"></dd></dl>

It follows that the smaller set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\neg ,\land ,\lor \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\neg ,\land ,\lor \}}</annotation>

</semantics>

</math><img src="./66b8dad6246e3a501c7ebb4be34b16512ce5b4e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.044ex; height:2.843ex;" alt="{\displaystyle \{\neg ,\land ,\lor \}}" loading="lazy"> is also functionally complete. (Its functional completeness is also proved by the <a href="Disjunctive_Normal_Form_Theorem" class="mw-redirect" title="Disjunctive Normal Form Theorem">Disjunctive Normal Form Theorem</a>.)<a href="#cite_note-:13-4">[4]</a> But this is still not minimal, as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lor }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lor }</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\lor B:=\neg (\neg A\land \neg B).}</annotation>

</semantics>

</math><img src="./80ecac5597cf2411ea362a3c381a864c7110abcb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.032ex; height:2.843ex;" alt="{\displaystyle A\lor B:=\neg (\neg A\land \neg B).}" loading="lazy"></dd></dl>

Alternatively, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \land }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \land }</annotation>

</semantics>

</math><img src="./d6823e5a222eb3ca49672818ac3d13ec607052c4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.009ex;" alt="{\displaystyle \land }" loading="lazy"> may be defined in terms of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lor }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lor }</annotation>

</semantics>

</math><img src="./ab47f6b1f589aedcf14638df1d63049d233d851a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.009ex;" alt="{\displaystyle \lor }" loading="lazy"> in a similar manner, or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lor }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lor }</annotation>

</semantics>

</math><img src="./ab47f6b1f589aedcf14638df1d63049d233d851a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.55ex; height:2.009ex;" alt="{\displaystyle \lor }" loading="lazy"> may be defined in terms of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rightarrow }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rightarrow }</annotation>

</semantics>

</math><img src="./53e574cc3aa5b4bf5f3f5906caf121a378eef08b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.843ex;" alt="{\displaystyle \rightarrow }" loading="lazy">:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ A\vee B:=\neg A\rightarrow B.}</annotation>

</semantics>

</math><img src="./ba054acdac8cea4efa434d83524aa58db607df2c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:19.734ex; height:2.176ex;" alt="{\displaystyle \ A\vee B:=\neg A\rightarrow B.}" loading="lazy"></dd></dl>

No further simplifications are possible. Hence, every two-element set of connectives containing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \neg }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \neg }</annotation>

</semantics>

</math><img src="./fa78fd02085d39aa58c9e47a6d4033ce41e02fad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.204ex; margin-bottom: -0.376ex; width:1.55ex; height:1.176ex;" alt="{\displaystyle \neg }" loading="lazy"> and one of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\land ,\lor ,\rightarrow \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\land ,\lor ,\rightarrow \}}</annotation>

</semantics>

</math><img src="./d7c28e44e1a3b887c8353339271739f8c37078d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.817ex; height:2.843ex;" alt="{\displaystyle \{\land ,\lor ,\rightarrow \}}" loading="lazy"> is a minimal functionally complete <a href="Subset" title="Subset">subset</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}}</annotation>

</semantics>

<div class="mw-heading mw-heading2"><h2 id="Formal_definition">Formal definition</h2></div>

Given the <a href="Boolean_domain" title="Boolean domain">Boolean domain</a> B = {0, 1}, a set F of Boolean functions fi : Bni → B is functionally complete if the <a href="Clone_(algebra)" title="Clone (algebra)">clone</a> on B generated by the basic functions fi contains all functions f : Bn → B, for all strictly positive integers n ≥ 1. In other words, the set is functionally complete if every Boolean function that takes at least one variable can be expressed in terms of the functions fi. Since every Boolean function of at least one variable can be expressed in terms of binary Boolean functions, F is functionally complete if and only if every binary Boolean function can be expressed in terms of the functions in F.

A more natural condition would be that the clone generated by F consist of all functions f : Bn → B, for all integers n ≥ 0. However, the examples given above are not functionally complete in this stronger sense because it is not possible to write a <a href="Arity" title="Arity">nullary</a> function, i.e. a constant expression, in terms of F if F itself does not contain at least one nullary function. With this stronger definition, the smallest functionally complete sets would have 2 elements.

Another natural condition would be that the clone generated by F together with the two nullary constant functions be functionally complete or, equivalently, functionally complete in the strong sense of the previous paragraph. The example of the Boolean function given by S(x, y, z) = z if x = y and S(x, y, z) = x otherwise shows that this condition is strictly weaker than functional completeness.<a href="#cite_note-Wesselkamper1975a-5">[5]</a><a href="#cite_note-Massey1975-6">[6]</a><a href="#cite_note-Wesselkamper1975b-7">[7]</a>

<div class="mw-heading mw-heading2"><h2 id="Characterization_of_functional_completeness">Characterization of functional completeness</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Post's_lattice" title="Post's lattice">Post's lattice</a></div>

<a href="Emil_Leon_Post" title="Emil Leon Post">Emil Post</a> proved that a set of logical connectives is functionally complete if and only if it is not a subset of any of the following sets of connectives:

<ul><li>The <a href="Monotonic" class="mw-redirect" title="Monotonic">monotonic</a> connectives; changing the truth value of any connected variables from F to T without changing any from T to F never makes these connectives change their return value from T to F, e.g. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \vee ,\wedge ,\top ,\bot }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vee ,\wedge ,\top ,\bot }</annotation>

</semantics>

</math><img src="./f22868c57609ee445a551d9b03f8bcccf96e8a20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.819ex; height:2.509ex;" alt="{\displaystyle \vee ,\wedge ,\top ,\bot }" loading="lazy">.</li>

<li>The <a href="Affine_transformation" title="Affine transformation">affine</a> connectives, such that each connected variable either always or never affects the truth value these connectives return, e.g. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow }</annotation>

</semantics>

</math><img src="./daec5e148d0c4e1bd354279114a8823a52beaf24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.95ex; height:2.509ex;" alt="{\displaystyle \neg ,\top ,\bot ,\leftrightarrow ,\nleftrightarrow }" loading="lazy">.</li>

<li>The self-dual connectives, which are equal to their own <a href="De_Morgan_dual" class="mw-redirect" title="De Morgan dual">de Morgan dual</a>; if the truth values of all variables are reversed, so is the truth value these connectives return, e.g. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \neg }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \neg }</annotation>

</semantics>

</math><img src="./fa78fd02085d39aa58c9e47a6d4033ce41e02fad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.204ex; margin-bottom: -0.376ex; width:1.55ex; height:1.176ex;" alt="{\displaystyle \neg }" loading="lazy">, <a href="Majority_function" title="Majority function">maj</a>(p, q, r).</li>

<li>The truth-preserving connectives; they return the <a href="Truth_value" title="Truth value">truth value</a> T under any interpretation that assigns T to all variables, e.g. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow }</annotation>

</semantics>

</math><img src="./9fb078948a0519a9b517b1e95363c608ac6c32c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.692ex; height:2.509ex;" alt="{\displaystyle \vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow }" loading="lazy">.</li>

<li>The falsity-preserving connectives; they return the truth value F under any interpretation that assigns F to all variables, e.g. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow }</annotation>

</semantics>

</math><img src="./31251967de0c2982527a26c567d2f08f294765a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.692ex; height:2.509ex;" alt="{\displaystyle \vee ,\wedge ,\bot ,\nrightarrow ,\nleftrightarrow }" loading="lazy">.</li></ul>

Post gave a complete description of the <a href="Lattice_(order)" title="Lattice (order)">lattice</a> of all <a href="Clone_(algebra)" title="Clone (algebra)">clones</a> (sets of operations closed under composition and containing all projections) on the two-element set {T, F}, nowadays called <a href="Post's_lattice" title="Post's lattice">Post's lattice</a>, which implies the above result as a simple corollary: the five mentioned sets of connectives are exactly the maximal nontrivial clones.<a href="#cite_note-8">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="Minimal_functionally_complete_operator_sets">Minimal functionally complete operator sets</h2></div>

When a single logical connective or Boolean operator is functionally complete by itself, it is called a Sheffer function<a href="#cite_note-Martin1989-9">[9]</a> or sometimes a sole sufficient operator. There are no <a href="Unary_operation" title="Unary operation">unary</a> operators with this property. <a href="Logical_NAND" class="mw-redirect" title="Logical NAND">NAND</a> and <a href="Logical_NOR" title="Logical NOR">NOR</a>, which are <a href="Boolean_algebra#Duality_principle" title="Boolean algebra">dual to each other</a>, are the only two binary Sheffer functions. These were discovered, but not published, by <a href="Charles_Sanders_Peirce" title="Charles Sanders Peirce">Charles Sanders Peirce</a> around 1880, and rediscovered independently and published by <a href="Henry_M._Sheffer" title="Henry M. Sheffer">Henry M. Sheffer</a> in 1913.<a href="#cite_note-Scharle1965-10">[10]</a>

In digital electronics terminology, the binary <a href="NAND_gate" title="NAND gate">NAND gate</a> (↑) and the binary <a href="NOR_gate" title="NOR gate">NOR gate</a> (↓) are the only binary <a href="Universal_logic_gate" class="mw-redirect" title="Universal logic gate">universal logic gates</a>.

The following are the minimal functionally complete sets of logical connectives with <a href="Arity" title="Arity">arity</a> ≤ 2:<a href="#cite_note-Wernick-11">[11]</a>

<dl><dt>One element</dt>

<dt>Two elements</dt>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\vee ,\neg \}}</annotation>

</semantics>

</math><img src="./e2e9c0ba8d7e6d25eb7b7c42514a8e5455533aa0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.46ex; height:2.843ex;" alt="{\displaystyle \{\vee ,\neg \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\wedge ,\neg \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\wedge ,\neg \}}</annotation>

</semantics>

</math><img src="./cea2d696984c094e742f17b4a0980812c34c5311.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.46ex; height:2.843ex;" alt="{\displaystyle \{\wedge ,\neg \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\to ,\neg \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\to ,\neg \}}</annotation>

</semantics>

</math><img src="./ce75e2f3daac9cec837fe974c6afd887701b5a64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.233ex; height:2.843ex;" alt="{\displaystyle \{\to ,\neg \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\gets ,\neg \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\gets ,\neg \}}</annotation>

</semantics>

</math><img src="./8e85dd5c575acd2855f93a08b102eabb6a2c2086.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.233ex; height:2.843ex;" alt="{\displaystyle \{\gets ,\neg \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\to ,\bot \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\to ,\bot \}}</annotation>

</semantics>

</math><img src="./55ebcc40157f1c4fb9352bcda77afdcfe135b11b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.491ex; height:2.843ex;" alt="{\displaystyle \{\to ,\bot \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\gets ,\bot \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\gets ,\bot \}}</annotation>

</semantics>

</math><img src="./7fcc3d747c0f79a70db6878511e5008e48df1c95.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.491ex; height:2.843ex;" alt="{\displaystyle \{\gets ,\bot \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\to ,\nleftrightarrow \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\to ,\nleftrightarrow \}}</annotation>

</semantics>

</math><img src="./b2d41b0afc20bb0ee130b470c495068a8771adb4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.006ex; height:2.843ex;" alt="{\displaystyle \{\to ,\nleftrightarrow \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\gets ,\nleftrightarrow \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\gets ,\nleftrightarrow \}}</annotation>

</semantics>

</math><img src="./25a8500d440a083dec2165e932ec595f2bd2190a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.006ex; height:2.843ex;" alt="{\displaystyle \{\gets ,\nleftrightarrow \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\to ,\nrightarrow \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\to ,\nrightarrow \}}</annotation>

</semantics>

</math><img src="./ead9c6cca0d49e461ddc6772d82b6d6d367b4d61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.006ex; height:2.843ex;" alt="{\displaystyle \{\to ,\nrightarrow \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\to ,\nleftarrow \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\to ,\nleftarrow \}}</annotation>

</semantics>

</math><img src="./daab405ca48bd7c7e387d635272447b59dd88a0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.006ex; height:2.843ex;" alt="{\displaystyle \{\to ,\nleftarrow \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\gets ,\nrightarrow \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\gets ,\nrightarrow \}}</annotation>

</semantics>

</math><img src="./5983419b30c5273441d0dc24b634b8206fe1c678.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.006ex; height:2.843ex;" alt="{\displaystyle \{\gets ,\nrightarrow \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\gets ,\nleftarrow \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\gets ,\nleftarrow \}}</annotation>

</semantics>

</math><img src="./54bb952bacbeef29cd08883ae5eb3619f32b103a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.006ex; height:2.843ex;" alt="{\displaystyle \{\gets ,\nleftarrow \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\nrightarrow ,\neg \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\nrightarrow ,\neg \}}</annotation>

</semantics>

</math><img src="./b20fab34e5fb82fefa38d5066ad53924c3bce448.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.233ex; height:2.843ex;" alt="{\displaystyle \{\nrightarrow ,\neg \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\nleftarrow ,\neg \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\nleftarrow ,\neg \}}</annotation>

</semantics>

</math><img src="./43288ebe50fa63d70ef9157560434678ca37ba48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.233ex; height:2.843ex;" alt="{\displaystyle \{\nleftarrow ,\neg \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\nrightarrow ,\top \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\nrightarrow ,\top \}}</annotation>

</semantics>

</math><img src="./ed8a953e72b9d747fc5b8ce20875c0851ec5029f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.491ex; height:2.843ex;" alt="{\displaystyle \{\nrightarrow ,\top \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\nleftarrow ,\top \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\nleftarrow ,\top \}}</annotation>

</semantics>

</math><img src="./5206ca5d7c500efe3089b24d9808cde1dd705db7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.491ex; height:2.843ex;" alt="{\displaystyle \{\nleftarrow ,\top \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\nrightarrow ,\leftrightarrow \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\nrightarrow ,\leftrightarrow \}}</annotation>

</semantics>

</math><img src="./653c466be112e74751723a7139883dc2d5e7d4a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.006ex; height:2.843ex;" alt="{\displaystyle \{\nrightarrow ,\leftrightarrow \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\nleftarrow ,\leftrightarrow \}.}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\nleftarrow ,\leftrightarrow \}.}</annotation>

</semantics>

</math><img src="./a6dc0da57d0ae529b13fad55a6881947444d5976.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.653ex; height:2.843ex;" alt="{\displaystyle \{\nleftarrow ,\leftrightarrow \}.}" loading="lazy"></dd>

<dt>Three elements</dt>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\lor ,\leftrightarrow ,\bot \}}</annotation>

</semantics>

</math><img src="./18c4d581f0cfe84e08c450cc07d3f2fb33fb1842.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.075ex; height:2.843ex;" alt="{\displaystyle \{\lor ,\leftrightarrow ,\bot \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}</annotation>

</semantics>

</math><img src="./634408661bb912f434b14ec6561f21d74b2af415.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.591ex; height:2.843ex;" alt="{\displaystyle \{\lor ,\leftrightarrow ,\nleftrightarrow \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\lor ,\nleftrightarrow ,\top \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\lor ,\nleftrightarrow ,\top \}}</annotation>

</semantics>

</math><img src="./acf8252f4312b6a20a7f0f2ca495aed3f7cb861e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.075ex; height:2.843ex;" alt="{\displaystyle \{\lor ,\nleftrightarrow ,\top \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\land ,\leftrightarrow ,\bot \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\land ,\leftrightarrow ,\bot \}}</annotation>

</semantics>

</math><img src="./7b45580e38a2f5365ddb6aa6c736d061dd71b601.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.075ex; height:2.843ex;" alt="{\displaystyle \{\land ,\leftrightarrow ,\bot \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}</annotation>

</semantics>

</math><img src="./d83f94b1b629f429470d329fc4c35af42068f797.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.591ex; height:2.843ex;" alt="{\displaystyle \{\land ,\leftrightarrow ,\nleftrightarrow \}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\land ,\nleftrightarrow ,\top \}.}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\land ,\nleftrightarrow ,\top \}.}</annotation>

</semantics>

</math><img src="./208d869de19e54e8c020727ff1a237efb0086f40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.722ex; height:2.843ex;" alt="{\displaystyle \{\land ,\nleftrightarrow ,\top \}.}" loading="lazy"></dd></dl>

There are no minimal functionally complete sets of more than three at most binary logical connectives.<a href="#cite_note-Wernick-11">[11]</a> In order to keep the lists above readable, operators that ignore one or more inputs have been omitted. For example, an operator that ignores the first input and outputs the negation of the second can be replaced by a unary negation.

<a href="Alfred_Tarski" title="Alfred Tarski">Alfred Tarski</a>'s paper "On the Primitive Term of Logistic" proved that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\leftrightarrow \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\leftrightarrow \}}</annotation>

</semantics>

</math><img src="./4dbc87a9fdffd238ae82b45c676f77c1debf0b45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.649ex; height:2.843ex;" alt="{\displaystyle \{\leftrightarrow \}}" loading="lazy"> is functionally complete,<a href="#cite_note-12">[12]</a> but this only works if quantification over propositions (a device from <a href="Second-order_logic" title="Second-order logic">second-order logic</a>) is used, so it doesn't count for the above list.

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<ul><li>Examples of using the <code>NAND</code> (↑) completeness. As illustrated by,<a href="#cite_note-13">[13]</a>

<li>Examples of using the <code>NOR</code> (↓) completeness. As illustrated by,<a href="#cite_note-14">[14]</a>

Note that an electronic circuit or a software function can be optimized by reuse, to reduce the number of gates. For instance, the "A ∧ B" operation, when expressed by ↑ gates, is implemented with the reuse of "A ↑ B",

<div class="mw-heading mw-heading2"><h2 id="In_other_domains">In other domains</h2></div>

Apart from logical connectives (Boolean operators), functional completeness can be introduced in other domains. For example, a set of <a href="Reversible_computation" class="mw-redirect" title="Reversible computation">reversible</a> gates is called functionally complete, if it can express every reversible operator.

The 3-input <a href="Fredkin_gate" title="Fredkin gate">Fredkin gate</a> is functionally complete reversible gate by itself – a sole sufficient operator. There are many other three-input universal logic gates, such as the <a href="Toffoli_gate" title="Toffoli gate">Toffoli gate</a>.

In <a href="Quantum_computing" title="Quantum computing">quantum computing</a>, the <a href="Hadamard_gate" class="mw-redirect" title="Hadamard gate">Hadamard gate</a> and the <a href="Quantum_logic_gate#Phase_shift_gates" title="Quantum logic gate">T gate</a> are universal, albeit with a <a href="Quantum_logic_gate#Universal_quantum_gates" title="Quantum logic gate">slightly more restrictive definition</a> than that of functional completeness.

<div class="mw-heading mw-heading2"><h2 id="Set_theory">Set theory</h2></div>

There is an <a href="Isomorphism" title="Isomorphism">isomorphism</a> between the <a href="Algebra_of_sets" title="Algebra of sets">algebra of sets</a> and the <a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a>, that is, they have the same <a href="Boolean_algebra_(structure)" title="Boolean algebra (structure)">structure</a>. Then, if we map boolean operators into set operators, the "translated" above text are valid also for sets: there are many "minimal complete set of set-theory operators" that can generate any other set relations. The more popular "Minimal complete operator sets" are {¬, ∩} and {¬, ∪}. If the <a href="Universal_set" title="Universal set">universal set</a> <a href="Russell's_Paradox" class="mw-redirect" title="Russell's Paradox">is forbidden</a>, set operators are restricted to being falsity (Ø) preserving, and cannot be equivalent to functionally complete Boolean algebra.

<ul><li><a href="Algebra_of_sets" title="Algebra of sets">Algebra of sets</a> – Identities and relationships involving sets</li>

<li><a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a> – Algebraic manipulation of "true" and "false"</li>

<li><a href="Completeness_(logic)" title="Completeness (logic)">Completeness (logic)</a> – Characteristic of some logical systems</li>

<li><a href="Conjunction/disjunction_duality" title="Conjunction/disjunction duality">Conjunction/disjunction duality</a> – Properties linking logical conjunction and disjunction</li>

<li><a href="List_of_Boolean_algebra_topics" title="List of Boolean algebra topics">List of Boolean algebra topics</a></li>

<li><a href="NAND_logic" title="NAND logic">NAND logic</a> – Logic constructed only from NAND gates</li>

<li><a href="NOR_logic" title="NOR logic">NOR logic</a> – Making other gates using just NOR gates</li>

<li><a href="One-instruction_set_computer" title="One-instruction set computer">One-instruction set computer</a> – Abstract machine that uses only one instruction</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFEnderton2001" class="citation cs2">Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Boston, MA: <a href="Academic_Press" title="Academic Press">Academic Press</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-12-238452-3</bdi></cite>. ("Complete set of logical connectives").

</li>

<li id="cite_note-Nolt1998-2"><a href="#cite_ref-Nolt1998_2-0">^</a> <cite id="CITEREFNoltRohatynVarzi1998" class="citation cs2">Nolt, John; Rohatyn, Dennis; Varzi, Achille (1998), Schaum's outline of theory and problems of logic (2nd ed.), New York: <a href="McGraw%E2%80%93Hill" class="mw-redirect" title="McGraw–Hill">McGraw–Hill</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-07-046649-4</bdi></cite>. ("[F]unctional completeness of [a] set of logical operators").

</li>

<li id="cite_note-Smith2003-3"><a href="#cite_ref-Smith2003_3-0">^</a> <cite id="CITEREFSmith2003" class="citation cs2">Smith, Peter (2003), An introduction to formal logic, <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-00804-4</bdi></cite>. (Defines "expressively adequate", shortened to "adequate set of connectives" in a section heading.)

</li>

<li id="cite_note-:13-4"><a href="#cite_ref-:13_4-0">^</a> <cite id="CITEREFHowson1997" class="citation book cs1">Howson, Colin (1997). Logic with trees: an introduction to symbolic logic. London; New York: Routledge. p. 41. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-415-13342-5</bdi>.</cite>

</li>

<cite id="CITEREFWesselkamper,_T.C.1975" class="citation cs2">Wesselkamper, T.C. (1975), <a rel="nofollow" class="external text" href="http://projecteuclid.org/euclid.ndjfl/1093891614">"A sole sufficient operator"</a>, Notre Dame Journal of Formal Logic, 16: 86–88, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1305%2Fndjfl%2F1093891614">10.1305/ndjfl/1093891614</a></cite>

</li>

<cite id="CITEREFMassey,_G.J.1975" class="citation cs2">Massey, G.J. (1975), <a rel="nofollow" class="external text" href="http://projecteuclid.org/euclid.ndjfl/1093891898">"Concerning an alleged Sheffer function"</a>, Notre Dame Journal of Formal Logic, 16 (4): 549–550, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1305%2Fndjfl%2F1093891898">10.1305/ndjfl/1093891898</a></cite>

</li>

<cite id="CITEREFWesselkamper,_T.C.1975" class="citation cs2">Wesselkamper, T.C. (1975), <a rel="nofollow" class="external text" href="http://projecteuclid.org/euclid.ndjfl/1093891899">"A Correction To My Paper" A. Sole Sufficient Operator"</a>, Notre Dame Journal of Formal Logic, 16 (4): 551, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1305%2Fndjfl%2F1093891899">10.1305/ndjfl/1093891899</a></cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFEmil_Leon_Post1941" class="citation book cs1">Emil Leon Post (1941). <a rel="nofollow" class="external text" href="https://dokumen.pub/qdownload/the-two-valued-iterative-systems-of-mathematical-logic-am-5-volume-5-9781400882366.html">The Two-Valued Iterative Systems of Mathematical Logic</a>. Annals of Mathematics studies. Vol. 5. Princeton: Princeton University Press. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1515%2F9781400882366">10.1515/9781400882366</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781400882366</bdi>.</cite> <code class="cs1-code">{{cite book}}</code>: ISBN / Date incompatibility (help) See p.105 for the theorem, pp.53, 59, 69, 70, 131 for a definition of the classes A1, L1, C2, C3, D3, and pp.35, 43 for the definition of [A:a] condition and α, β, γ function.

</li>

<li id="cite_note-Martin1989-9"><a href="#cite_ref-Martin1989_9-0">^</a> The term was originally restricted to binary operations, but since the end of the 20th century it is used more generally.

<cite id="CITEREFMartin,_N.M.1989" class="citation cs2">Martin, N.M. (1989), Systems of logic, Cambridge University Press, p. 54, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-36770-7</bdi></cite>.

</li>

<cite id="CITEREFScharle,_T.W.1965" class="citation cs2">Scharle, T.W. (1965), <a rel="nofollow" class="external text" href="http://projecteuclid.org/euclid.ndjfl/1093958259">"Axiomatization of propositional calculus with Sheffer functors"</a>, Notre Dame J. Formal Logic, 6 (3): 209–217, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1305%2Fndjfl%2F1093958259">10.1305/ndjfl/1093958259</a></cite>.

</li>

<li id="cite_note-Wernick-11">^ <a href="#cite_ref-Wernick_11-0">a</a> <a href="#cite_ref-Wernick_11-1">b</a> Wernick, William (1942) "Complete Sets of Logical Functions," Transactions of the American Mathematical Society 51: 117–32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \nleftarrow }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nleftarrow }</annotation>

</semantics>

</math><img src="./7694c9fc8eebe8a57c8156dd3c2caf022a619439.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.137ex; margin-bottom: -0.308ex; width:2.324ex; height:1.509ex;" alt="{\displaystyle \nleftarrow }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \nrightarrow }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \nrightarrow }</annotation>

</semantics>

</math><img src="./4c458d67617e028ed10948d2dbcfef80e9e060a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.137ex; margin-bottom: -0.308ex; width:2.324ex; height:1.509ex;" alt="{\displaystyle \nrightarrow }" loading="lazy">.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFTajtelbaum-Tarski1998" class="citation cs2">Tajtelbaum-Tarski, Alfred (1998), Srzednicki, Jan T. J.; Stachniak, Zbigniew (eds.), <a rel="nofollow" class="external text" href="https://doi.org/10.1007/978-94-011-5736-0_3">"On the Primitive Term of Logistic"</a>, Leśniewski’s Systems Protothetic, Dordrecht: Springer Netherlands, pp. 43–68, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-94-011-5736-0_3">10.1007/978-94-011-5736-0_3</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-94-011-5736-0</bdi>, retrieved 2025-08-03</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> "NAND Gate Operations" at <a rel="nofollow" class="external free" href="http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html">http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nand.html</a>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> "NOR Gate Operations" at <a rel="nofollow" class="external free" href="http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html">http://hyperphysics.phy-astr.gsu.edu/hbase/electronic/nor.html</a>

</li>

</ol></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Mathematical_logic344" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Mathematical_logic344" style="font-size:114%;margin:0 4em"><a href="Mathematical_logic" title="Mathematical logic">Mathematical logic</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Axiom" title="Axiom">Axiom</a>

<li><a href="Cardinality" title="Cardinality">Cardinality</a></li>

<li><a href="First-order_logic" title="First-order logic">First-order logic</a></li>

<li><a href="Formal_proof" title="Formal proof">Formal proof</a></li>

<li><a href="Formal_semantics_(logic)" class="mw-redirect" title="Formal semantics (logic)">Formal semantics</a></li>

<li><a href="Foundations_of_mathematics" title="Foundations of mathematics">Foundations of mathematics</a></li>

<li><a href="Information_theory" title="Information theory">Information theory</a></li>

<li><a href="Lemma_(mathematics)" title="Lemma (mathematics)">Lemma</a></li>

<li><a href="Logical_consequence" title="Logical consequence">Logical consequence</a></li>

<li><a href="Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a></li>

<li><a href="Theorem" title="Theorem">Theorem</a></li>

<li><a href="Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a></li>

<li><a href="Type_theory" title="Type theory">Type theory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems (list)  and <a href="Paradoxes_of_set_theory" title="Paradoxes of set theory">paradoxes</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="G%C3%B6del's_completeness_theorem" title="Gödel's completeness theorem">Gödel's completeness</a> and <a href="G%C3%B6del's_incompleteness_theorems" title="Gödel's incompleteness theorems">incompleteness theorems</a></li>

<li><a href="Tarski's_undefinability_theorem" title="Tarski's undefinability theorem">Tarski's undefinability</a></li>

<li><a href="Banach%E2%80%93Tarski_paradox" title="Banach–Tarski paradox">Banach–Tarski paradox</a></li>

<li>Cantor's <a href="Cantor's_theorem" title="Cantor's theorem">theorem,</a> <a href="Cantor's_paradox" title="Cantor's paradox">paradox</a> and <a href="Cantor's_diagonal_argument" title="Cantor's diagonal argument">diagonal argument</a></li>

<li><a href="Compactness_theorem" title="Compactness theorem">Compactness</a></li>

<li><a href="Halting_problem" title="Halting problem">Halting problem</a></li>

<li><a href="Lindstr%C3%B6m's_theorem" title="Lindström's theorem">Lindström's</a></li>

<li><a href="L%C3%B6wenheim%E2%80%93Skolem_theorem" title="Löwenheim–Skolem theorem">Löwenheim–Skolem</a></li>

<li><a href="Russell's_paradox" title="Russell's paradox">Russell's paradox</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Logic" title="Logic">Logics</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Traditional95" scope="row" class="navbox-group" style="width:1%"><a href="Term_logic" title="Term logic">Traditional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Classical_logic" title="Classical logic">Classical logic</a></li>

<li><a href="Logical_truth" title="Logical truth">Logical truth</a></li>

<li><a href="Tautology_(logic)" title="Tautology (logic)">Tautology</a></li>

<li><a href="Proposition" title="Proposition">Proposition</a></li>

<li><a href="Inference" title="Inference">Inference</a></li>

<li><a href="Logical_equivalence" title="Logical equivalence">Logical equivalence</a></li>

<li><a href="Consistency" title="Consistency">Consistency</a>

<ul><li><a href="Equiconsistency" title="Equiconsistency">Equiconsistency</a></li></ul></li>

<li><a href="Argument" title="Argument">Argument</a></li>

<li><a href="Soundness" title="Soundness">Soundness</a></li>

<li><a href="Validity_(logic)" title="Validity (logic)">Validity</a></li>

<li><a href="Syllogism" title="Syllogism">Syllogism</a></li>

<li><a href="Square_of_opposition" title="Square of opposition">Square of opposition</a></li>

<li><a href="Venn_diagram" title="Venn diagram">Venn diagram</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a></li>

<li><a href="Boolean_function" title="Boolean function">Boolean functions</a></li>

<li><a href="Logical_connective" title="Logical connective">Logical connectives</a></li>

<li><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional calculus</a></li>

<li><a href="Propositional_formula" title="Propositional formula">Propositional formula</a></li>

<li><a href="Truth_table" title="Truth table">Truth tables</a></li>

<li><a href="Many-valued_logic" title="Many-valued logic">Many-valued logic</a>

<li><a href="Finite-valued_logic" title="Finite-valued logic">finite</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Predicate_logic" class="mw-redirect" title="Predicate logic">Predicate</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="First-order_logic" title="First-order logic">First-order</a>

<li><a href="Second-order_logic" title="Second-order logic">Second-order</a>

<ul><li><a href="Monadic_second-order_logic" title="Monadic second-order logic">Monadic</a></li></ul></li>

<li><a href="Higher-order_logic" title="Higher-order logic">Higher-order</a></li>

<li><a href="Fixed-point_logic" title="Fixed-point logic">Fixed-point</a></li>

<li><a href="Quantifier_(logic)" title="Quantifier (logic)">Quantifiers</a></li>

<li><a href="Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a></li>

<li><a href="Monadic_predicate_calculus" title="Monadic predicate calculus">Monadic predicate calculus</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Set_theory" title="Set theory">Set theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Hereditary_set" title="Hereditary set">hereditary</a></li></ul></li>

<li><a href="Class_(set_theory)" title="Class (set theory)">Class</a></li>

<li>(<a href="Urelement" title="Urelement">Ur-</a>)<a href="Element_(mathematics)" title="Element (mathematics)">Element</a></li>

<li><a href="Ordinal_number" title="Ordinal number">Ordinal number</a></li>

<li><a href="Extensionality" title="Extensionality">Extensionality</a></li>

<li><a href="Forcing_(mathematics)" title="Forcing (mathematics)">Forcing</a></li>

<li><a href="Relation_(mathematics)" title="Relation (mathematics)">Relation</a>

<ul><li><a href="Equivalence_relation" title="Equivalence relation">equivalence</a></li>

<li><a href="Partition_of_a_set" title="Partition of a set">partition</a></li></ul></li>

<li>Set operations:

<ul><li><a href="Intersection_(set_theory)" title="Intersection (set theory)">intersection</a></li>

<li><a href="Union_(set_theory)" title="Union (set theory)">union</a></li>

<li><a href="Complement_(set_theory)" title="Complement (set theory)">complement</a></li>

<li><a href="Cartesian_product" title="Cartesian product">Cartesian product</a></li>

<li><a href="Power_set" title="Power set">power set</a></li>

<li><a href="List_of_set_identities_and_relations" title="List of set identities and relations">identities</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types of <a href="Set_(mathematics)" title="Set (mathematics)">sets</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Countable_set" title="Countable set">Countable</a></li>

<li><a href="Uncountable_set" title="Uncountable set">Uncountable</a></li>

<li><a href="Empty_set" title="Empty set">Empty</a></li>

<li><a href="Inhabited_set" title="Inhabited set">Inhabited</a></li>

<li><a href="Singleton_(mathematics)" title="Singleton (mathematics)">Singleton</a></li>

<li><a href="Finite_set" title="Finite set">Finite</a></li>

<li><a href="Infinite_set" title="Infinite set">Infinite</a></li>

<li><a href="Transitive_set" title="Transitive set">Transitive</a></li>

<li><a href="Ultrafilter_(set_theory)" class="mw-redirect" title="Ultrafilter (set theory)">Ultrafilter</a></li>

<li><a href="Recursive_set" class="mw-redirect" title="Recursive set">Recursive</a></li>

<li><a href="Fuzzy_set" title="Fuzzy set">Fuzzy</a></li>

<li><a href="Universal_set" title="Universal set">Universal</a></li>

<li><a href="Universe_(mathematics)" title="Universe (mathematics)">Universe</a>

<ul><li><a href="Constructible_universe" title="Constructible universe">constructible</a></li>

<li><a href="Grothendieck_universe" title="Grothendieck universe">Grothendieck</a></li>

<li><a href="Von_Neumann_universe" title="Von Neumann universe">Von Neumann</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Map_(mathematics)" title="Map (mathematics)">Maps</a> and <a href="Cardinality" title="Cardinality">cardinality</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Function_(mathematics)" title="Function (mathematics)">Function</a>/<a href="Map_(mathematics)" title="Map (mathematics)">Map</a>

<ul><li><a href="Domain_of_a_function" title="Domain of a function">domain</a></li>

<li><a href="Codomain" title="Codomain">codomain</a></li>

<li><a href="Image_(mathematics)" title="Image (mathematics)">image</a></li></ul></li>

<li><a href="Injective_function" title="Injective function">In</a>/<a href="Surjective_function" title="Surjective function">Sur</a>/<a href="Bijection" title="Bijection">Bi</a>-jection</li>

<li><a href="Schr%C3%B6der%E2%80%93Bernstein_theorem" title="Schröder–Bernstein theorem">Schröder–Bernstein theorem</a></li>

<li><a href="Isomorphism" title="Isomorphism">Isomorphism</a></li>

<li><a href="G%C3%B6del_numbering" title="Gödel numbering">Gödel numbering</a></li>

<li><a href="Enumeration" title="Enumeration">Enumeration</a></li>

<li><a href="Large_cardinal" title="Large cardinal">Large cardinal</a>

<ul><li><a href="Inaccessible_cardinal" title="Inaccessible cardinal">inaccessible</a></li></ul></li>

<li><a href="Aleph_number" title="Aleph number">Aleph number</a></li>

<li><a href="Operation_(mathematics)" title="Operation (mathematics)">Operation</a>

<ul><li><a href="Binary_operation" title="Binary operation">binary</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Set theories</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Zermelo%E2%80%93Fraenkel_set_theory" title="Zermelo–Fraenkel set theory">Zermelo–Fraenkel</a>

<ul><li><a href="Axiom_of_choice" title="Axiom of choice">axiom of choice</a></li>

<li><a href="Continuum_hypothesis" title="Continuum hypothesis">continuum hypothesis</a></li></ul></li>

<li><a href="General_set_theory" title="General set theory">General</a></li>

<li><a href="Kripke%E2%80%93Platek_set_theory" title="Kripke–Platek set theory">Kripke–Platek</a></li>

<li><a href="Morse%E2%80%93Kelley_set_theory" title="Morse–Kelley set theory">Morse–Kelley</a></li>

<li><a href="Naive_set_theory" title="Naive set theory">Naive</a></li>

<li><a href="New_Foundations" title="New Foundations">New Foundations</a></li>

<li><a href="Tarski%E2%80%93Grothendieck_set_theory" title="Tarski–Grothendieck set theory">Tarski–Grothendieck</a></li>

<li><a href="Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory" title="Von Neumann–Bernays–Gödel set theory">Von Neumann–Bernays–Gödel</a></li>

<li><a href="Ackermann_set_theory" title="Ackermann set theory">Ackermann</a></li>

<li><a href="Constructive_set_theory" title="Constructive set theory">Constructive</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Formal_system" title="Formal system">Formal systems</a> (<a href="List_of_formal_systems" title="List of formal systems">list</a>), <a href="Formal_language" title="Formal language">language</a> and <a href="Syntax_(logic)" title="Syntax (logic)">syntax</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alphabet_(formal_languages)" title="Alphabet (formal languages)">Alphabet</a></li>

<li><a href="Arity" title="Arity">Arity</a></li>

<li><a href="Automata_theory" title="Automata theory">Automata</a></li>

<li><a href="Axiom_schema" title="Axiom schema">Axiom schema</a></li>

<li><a href="Expression_(mathematics)" title="Expression (mathematics)">Expression</a>

<ul><li><a href="Ground_expression" title="Ground expression">ground</a></li></ul></li>

<li><a href="Extension_by_new_constant_and_function_names" title="Extension by new constant and function names">Extension</a>

<ul><li><a href="Extension_by_definitions" class="mw-redirect" title="Extension by definitions">by definition</a></li>

<li><a href="Conservative_extension" title="Conservative extension">conservative</a></li></ul></li>

<li><a href="Finitary_relation" title="Finitary relation">Relation</a></li>

<li><a href="Formation_rule" title="Formation rule">Formation rule</a></li>

<li><a href="Formal_grammar" title="Formal grammar">Grammar</a></li>

<li><a href="Well-formed_formula" title="Well-formed formula">Formula</a>

<ul><li><a href="Atomic_formula" title="Atomic formula">atomic</a></li>

<li><a href="Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">closed</a></li>

<li><a href="Ground_formula" class="mw-redirect" title="Ground formula">ground</a></li>

<li><a href="Free_variables_and_bound_variables" title="Free variables and bound variables">Free/bound variable</a></li>

<li><a href="Formal_language" title="Formal language">Language</a></li>

<li><a href="Metalanguage" title="Metalanguage">Metalanguage</a></li>

<li><a href="Logical_connective" title="Logical connective">Logical connective</a>

<li><a href="Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a>

<ul><li><a href="Functional_predicate" title="Functional predicate">functional</a></li>

<li><a href="Predicate_variable" title="Predicate variable">variable</a></li>

<li><a href="Propositional_variable" title="Propositional variable">propositional variable</a></li></ul></li>

<li><a href="Formal_proof" title="Formal proof">Proof</a></li>

<li><a href="Quantifier_(logic)" title="Quantifier (logic)">Quantifier</a>

<li><a href="Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">Sentence</a>

<ul><li><a href="Atomic_sentence" title="Atomic sentence">atomic</a></li>

<li><a href="Spectrum_of_a_sentence" title="Spectrum of a sentence">spectrum</a></li></ul></li>

<li><a href="Signature_(logic)" title="Signature (logic)">Signature</a></li>

<li><a href="String_(formal_languages)" class="mw-redirect" title="String (formal languages)">String</a></li>

<li><a href="Substitution_(logic)" title="Substitution (logic)">Substitution</a></li>

<li><a href="Symbol_(formal)" title="Symbol (formal)">Symbol</a>

<ul><li><a href="Uninterpreted_function" title="Uninterpreted function">function</a></li>

<li><a href="Logical_constant" title="Logical constant">logical/constant</a></li>

<li><a href="Non-logical_symbol" title="Non-logical symbol">non-logical</a></li>

<li><a href="Variable_(mathematics)" title="Variable (mathematics)">variable</a></li></ul></li>

<li><a href="Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Example <a href="Axiomatic_system" title="Axiomatic system">axiomatic systems</a> (<a href="List_of_first-order_theories" title="List of first-order theories">list</a>)</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>of <a href="True_arithmetic" title="True arithmetic">arithmetic</a>:

<ul><li><a href="Peano_axioms" title="Peano axioms">Peano</a></li>

<li><a href="Second-order_arithmetic" title="Second-order arithmetic">second-order</a></li>

<li><a href="Elementary_function_arithmetic" title="Elementary function arithmetic">elementary function</a></li>

<li><a href="Primitive_recursive_arithmetic" title="Primitive recursive arithmetic">primitive recursive</a></li>

<li><a href="Robinson_arithmetic" title="Robinson arithmetic">Robinson</a></li>

<li><a href="Skolem_arithmetic" title="Skolem arithmetic">Skolem</a></li></ul></li>

<li>of the <a href="Construction_of_the_real_numbers" title="Construction of the real numbers">real numbers</a>

<ul><li><a href="Tarski's_axiomatization_of_the_reals" title="Tarski's axiomatization of the reals">Tarski's axiomatization</a></li></ul></li>

<li>of <a href="Axiomatization_of_Boolean_algebras" class="mw-redirect" title="Axiomatization of Boolean algebras">Boolean algebras</a>

<ul><li><a href="Boolean_algebras_canonically_defined" title="Boolean algebras canonically defined">canonical</a></li>

<li><a href="Minimal_axioms_for_Boolean_algebra" title="Minimal axioms for Boolean algebra">minimal axioms</a></li></ul></li>

<li>of <a href="Foundations_of_geometry" title="Foundations of geometry">geometry</a>:

<ul><li><a href="Euclidean_geometry" title="Euclidean geometry">Euclidean</a>:

<ul><li><a href="Euclid's_Elements" title="Euclid's Elements">Elements</a></li>

<li><a href="Hilbert's_axioms" title="Hilbert's axioms">Hilbert's</a></li>

<li><a href="Tarski's_axioms" title="Tarski's axioms">Tarski's</a></li></ul></li>

<li><a href="Non-Euclidean_geometry" title="Non-Euclidean geometry">non-Euclidean</a></li></ul></li></ul>

<ul><li><a href="Principia_Mathematica" title="Principia Mathematica">Principia Mathematica</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Proof_theory" title="Proof theory">Proof theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Formal_proof" title="Formal proof">Formal proof</a></li>

<li><a href="Natural_deduction" title="Natural deduction">Natural deduction</a></li>

<li><a href="Logical_consequence" title="Logical consequence">Logical consequence</a></li>

<li><a href="Rule_of_inference" title="Rule of inference">Rule of inference</a></li>

<li><a href="Sequent_calculus" title="Sequent calculus">Sequent calculus</a></li>

<li><a href="Theorem" title="Theorem">Theorem</a></li>

<li><a href="Formal_system" title="Formal system">Systems</a>

<ul><li><a href="Axiomatic_system" title="Axiomatic system">axiomatic</a></li>

<li><a href="Deductive_system" class="mw-redirect" title="Deductive system">deductive</a></li>

<li><a href="Hilbert_system" title="Hilbert system">Hilbert</a>

<li><a href="Complete_theory" title="Complete theory">Complete theory</a></li>

<li><a href="Independence_(mathematical_logic)" title="Independence (mathematical logic)">Independence</a> (<a href="List_of_statements_independent_of_ZFC" title="List of statements independent of ZFC">from ZFC</a>)</li>

<li><a href="Proof_of_impossibility" title="Proof of impossibility">Proof of impossibility</a></li>

<li><a href="Ordinal_analysis" title="Ordinal analysis">Ordinal analysis</a></li>

<li><a href="Reverse_mathematics" title="Reverse mathematics">Reverse mathematics</a></li>

<li><a href="Self-verifying_theories" title="Self-verifying theories">Self-verifying theories</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Model_theory" title="Model theory">Model theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interpretation_(logic)" title="Interpretation (logic)">Interpretation</a>

<ul><li><a href="Interpretation_function" class="mw-redirect" title="Interpretation function">function</a></li>

<li><a href="Interpretation_(model_theory)" title="Interpretation (model theory)">of models</a></li></ul></li>

<li><a href="Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a>

<ul><li><a href="Elementary_equivalence" title="Elementary equivalence">equivalence</a></li>

<li><a href="Finite_model_theory" title="Finite model theory">finite</a></li>

<li><a href="Saturated_model" title="Saturated model">saturated</a></li>

<li><a href="Spectrum_of_a_theory" title="Spectrum of a theory">spectrum</a></li>

<li><a href="Substructure_(mathematics)" title="Substructure (mathematics)">submodel</a></li></ul></li>

<li><a href="Non-standard_model" title="Non-standard model">Non-standard model</a>

<ul><li><a href="Non-standard_model_of_arithmetic" title="Non-standard model of arithmetic">of arithmetic</a></li></ul></li>

<li><a href="Diagram_(mathematical_logic)" title="Diagram (mathematical logic)">Diagram</a>

<ul><li><a href="Elementary_diagram" title="Elementary diagram">elementary</a></li></ul></li>

<li><a href="Categorical_theory" title="Categorical theory">Categorical theory</a></li>

<li><a href="Model_complete_theory" title="Model complete theory">Model complete theory</a></li>

<li><a href="Satisfiability" title="Satisfiability">Satisfiability</a></li>

<li><a href="Semantics_of_logic" title="Semantics of logic">Semantics of logic</a></li>

<li><a href="Strength_(mathematical_logic)" title="Strength (mathematical logic)">Strength</a></li>

<li><a href="Theories_of_truth" class="mw-redirect" title="Theories of truth">Theories of truth</a>

<ul><li><a href="Semantic_theory_of_truth" title="Semantic theory of truth">semantic</a></li>

<li><a href="Tarski's_theory_of_truth" class="mw-redirect" title="Tarski's theory of truth">Tarski's</a></li>

<li><a href="Kripke's_theory_of_truth" class="mw-redirect" title="Kripke's theory of truth">Kripke's</a></li></ul></li>

<li><a href="T-schema" title="T-schema">T-schema</a></li>

<li><a href="Transfer_principle" title="Transfer principle">Transfer principle</a></li>

<li><a href="Truth_predicate" title="Truth predicate">Truth predicate</a></li>

<li><a href="Truth_value" title="Truth value">Truth value</a></li>

<li><a href="Ultraproduct" title="Ultraproduct">Ultraproduct</a></li>

<li><a href="Validity_(logic)" title="Validity (logic)">Validity</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computability_theory" title="Computability theory">Computability theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Church_encoding" title="Church encoding">Church encoding</a></li>

<li><a href="Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a></li>

<li><a href="Computably_enumerable_set" title="Computably enumerable set">Computably enumerable</a></li>

<li><a href="Computable_function" title="Computable function">Computable function</a></li>

<li><a href="Computable_set" title="Computable set">Computable set</a></li>

<li><a href="Decision_problem" title="Decision problem">Decision problem</a>

<ul><li><a href="Decidability_(logic)" title="Decidability (logic)">decidable</a></li>

<li><a href="Undecidable_problem" title="Undecidable problem">undecidable</a></li>

<li><a href="P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a></li></ul></li>

<li><a href="Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li>

<li><a href="Lambda_calculus" title="Lambda calculus">Lambda calculus</a></li>

<li><a href="Primitive_recursive_function" title="Primitive recursive function">Primitive recursive function</a></li>

<li><a href="Recursion" title="Recursion">Recursion</a></li>

<li><a href="Recursive_set" class="mw-redirect" title="Recursive set">Recursive set</a></li>

<li><a href="Turing_machine" title="Turing machine">Turing machine</a></li>

<li><a href="Type_theory" title="Type theory">Type theory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Abstract_logic" title="Abstract logic">Abstract logic</a></li>

<li><a href="Algebraic_logic" title="Algebraic logic">Algebraic logic</a></li>

<li><a href="Automated_theorem_proving" title="Automated theorem proving">Automated theorem proving</a></li>

<li><a href="Category_theory" title="Category theory">Category theory</a></li>

<li><a href="Concrete_category" title="Concrete category">Concrete</a>/<a href="Category_(mathematics)" title="Category (mathematics)">Abstract category</a></li>

<li><a href="Category_of_sets" title="Category of sets">Category of sets</a></li>

<li><a href="History_of_logic" title="History of logic">History of logic</a></li>

<li><a href="History_of_mathematical_logic" class="mw-redirect" title="History of mathematical logic">History of mathematical logic</a>

<ul><li><a href="Timeline_of_mathematical_logic" title="Timeline of mathematical logic">timeline</a></li></ul></li>

<li><a href="Logicism" title="Logicism">Logicism</a></li>

<li><a href="Mathematical_object" title="Mathematical object">Mathematical object</a></li>

<li><a href="Philosophy_of_mathematics" title="Philosophy of mathematics">Philosophy of mathematics</a></li>

<li><a href="Supertask" title="Supertask">Supertask</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <a href="Portal%3AMathematics" title="Portal:Mathematics">Mathematics portal</a></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-03" href="https://en.wikipedia.org/wiki/?title=Functional_completeness&oldid=1303996974">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>